# 超时
# class Node:
#     def __init__(self, key, val):
#         self.key = key
#         self.val = val
#         self.next = None
#         self.prev = None
#         self.counter = 1
#
#
#
# class LFUCache(object):
#
#     def __init__(self, capacity):
#         """
#         :type capacity: int
#         """
#         self.max_len = capacity
#         self.d = {}
#         self.freq_table = {}
#         self.min_freq = 1
#         self.c = 0
#
#     def get(self, key):
#         """
#         :type key: int
#         :rtype: int
#         """
#         if self.max_len == 0:
#             return -1
#         if key not in self.d:
#             return -1
#         node = self.d[key]
#         node.counter += 1
#         r_value = node.val
#         next_node = node.next
#         while next_node and node.counter >= next_node.counter:
#             prev_node = node.prev
#             next_next = next_node.next
#             node.prev = next_node
#             next_node.next = node
#             next_node.prev = prev_node
#             if prev_node:
#                 prev_node.next = next_node
#             else:
#                 self.head = next_node
#             node.next = next_next
#             if next_next:
#                 next_next.prev = node
#             next_node = node.next
#         return r_value
#
#     def put(self, key, value):
#         """
#         :type key: int
#         :type value: int
#         :rtype: None
#         """
#         if self.max_len > 0:
#             if key not in self.d:
#                 node = Node(key, value)
#                 self.d[key] = node
#                 if self.c < self.max_len:
#                     self.c += 1
#                 else:
#                     self.d.pop(self.head.key)
#                     self.head = self.head.next
#                 node.next = self.head
#                 if self.head:
#                     self.head.prev = node
#                 next_node = self.head
#                 self.head = node
#             else:
#                 node = self.d[key]
#                 node.val = value
#                 node.counter += 1
#                 next_node = node.next
#             while next_node and node.counter >= next_node.counter:
#                 prev_node = node.prev
#                 next_next = next_node.next
#                 node.prev = next_node
#                 next_node.next = node
#                 next_node.prev = prev_node
#                 if prev_node:
#                     prev_node.next = next_node
#                 else:
#                     self.head = next_node
#                 node.next = next_next
#                 if next_next:
#                     next_next.prev = node
#                 next_node = node.next

# 按频率分别建表
class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None
        self.prev = None
        self.counter = 1


class LFUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.max_len = capacity
        self.d = {}
        self.freq_table = {}
        self.min_freq = 1
        self.c = 0

    def get(self, key):
        if self.max_len == 0:
            return -1
        if key not in self.d:
            return -1
        node = self.d[key]
        r_value = node.val
        node = self.d[key]
        freq = node.counter
        prev_node = node.prev
        next_node = node.next
        if prev_node.key == '#' and next_node.key == '#':
            self.freq_table.pop(freq)
            if self.min_freq == freq:
                self.min_freq += 1
        else:
            prev_node.next = next_node
            next_node.prev = prev_node
        node.counter += 1
        freq = node.counter
        if freq not in self.freq_table:
            self.freq_table[freq] = {}
            self.freq_table[freq]['head'] = Node('#', '#')
            self.freq_table[freq]['last'] = Node('#', '#')
            now_head = self.freq_table[freq]['head']
            now_last = self.freq_table[freq]['last']
            now_head.next = node
            node.next = now_last
            node.prev = now_head
            now_last.prev = node
        else:
            now_last = self.freq_table[freq]['last']
            prev_node = now_last.prev
            prev_node.next = node
            node.next = now_last
            node.prev = prev_node
            now_last.prev = node
        return r_value

    def put(self, key, value):
        if self.max_len > 0:
            if key not in self.d:
                node = Node(key, value)
                self.d[key] = node
                if self.c < self.max_len:
                    self.c += 1
                else:
                    head = self.freq_table[self.min_freq]['head'].next
                    self.d.pop(head.key)
                    if head.next.key != '#':
                        next_head = head.next
                        self.freq_table[self.min_freq]['head'].next = next_head
                        next_head.prev = self.freq_table[self.min_freq]['head']
                    else:
                        self.freq_table.pop(self.min_freq)
                self.min_freq = 1
                if self.min_freq not in self.freq_table:
                    self.freq_table[self.min_freq] = {}
                    self.freq_table[self.min_freq]['head'] = Node('#', '#')
                    self.freq_table[self.min_freq]['last'] = Node('#', '#')
                    now_head = self.freq_table[self.min_freq]['head']
                    now_last = self.freq_table[self.min_freq]['last']
                    now_head.next = node
                    node.next = now_last
                    node.prev = now_head
                    now_last.prev = node
                else:
                    now_last = self.freq_table[self.min_freq]['last']
                    prev_node = now_last.prev
                    prev_node.next = node
                    node.next = now_last
                    node.prev = prev_node
                    now_last.prev = node
            else:
                node = self.d[key]
                node.val = value
                freq = node.counter
                prev_node = node.prev
                next_node = node.next
                if prev_node.key == '#' and next_node.key == '#':
                    self.freq_table.pop(freq)
                    if self.min_freq == freq:
                        self.min_freq += 1
                else:
                    prev_node.next = next_node
                    next_node.prev = prev_node
                node.counter += 1
                freq = node.counter
                if freq not in self.freq_table:
                    self.freq_table[freq] = {}
                    self.freq_table[freq]['head'] = Node('#', '#')
                    self.freq_table[freq]['last'] = Node('#', '#')
                    now_head = self.freq_table[freq]['head']
                    now_last = self.freq_table[freq]['last']
                    now_head.next = node
                    node.next = now_last
                    node.prev = now_head
                    now_last.prev = node
                else:
                    now_last = self.freq_table[freq]['last']
                    prev_node = now_last.prev
                    prev_node.next = node
                    node.next = now_last
                    node.prev = prev_node
                    now_last.prev = node


obj = LFUCache(10)
obj.put(10, 13)
obj.put(3, 17)
obj.put(6, 11)
obj.put(10, 5)
obj.put(9, 10)
print(obj.get(13))
obj.put(2, 19)
print(obj.get(2))
print(obj.get(3))
obj.put(5, 25)
print(obj.get(8))
obj.put(9, 22)
obj.put(5, 5)
obj.put(1, 30)
print(obj.get(11))
obj.put(9, 12)
print(obj.get(7))
print(obj.get(5))
print(obj.get(8))
print(obj.get(9))
obj.put(4, 30)
obj.put(9, 3)
print(obj.get(9))
print(obj.get(10))
print(obj.get(10))
obj.put(6, 14)
obj.put(3, 1)
print(obj.get(3))
obj.put(10, 11)
print(obj.get(8))
obj.put(2, 14)
print(obj.get(1))
print(obj.get(5))
print(obj.get(4))
obj.put(11, 4)
obj.put(12, 24)
obj.put(5, 18)
print(obj.get(13))
obj.put(7, 23)
print(obj.get(8))
print(obj.get(12))
obj.put(3, 27)
obj.put(2, 12)
print(obj.get(5))
obj.put(2, 9)
obj.put(13, 4)
obj.put(8, 18)
obj.put(1, 7)
print(obj.get(6))
obj.put(9, 29)
obj.put(8, 21)
print(obj.get(5))
obj.put(6, 30)
obj.put(1, 12)
print(obj.get(10))
obj.put(4, 15)
obj.put(7, 22)
obj.put(11, 26)
obj.put(8, 17)
obj.put(9, 29)
print(obj.get(10))
obj.put(3, 4)
obj.put(11, 30)
print(obj.get(12))
